|
The Turán graph ''T''(''n'',''r'') is a complete multipartite graph formed by partitioning a set of ''n'' vertices into ''r'' subsets, with sizes as equal as possible, and connecting two vertices by an edge whenever they belong to different subsets. The graph will have subsets of size , and subsets of size . That is, it is a complete ''r''-partite graph : Each vertex has degree either or . The number of edges is : It is a regular graph, if ''n'' is divisible by ''r''. ==Turán's theorem== Turán graphs are named after Pál Turán, who used them to prove Turán's theorem, an important result in extremal graph theory. By the pigeonhole principle, every set of ''r'' + 1 vertices in the Turán graph includes two vertices in the same partition subset; therefore, the Turán graph does not contain a clique of size ''r'' + 1. According to Turán's theorem, the Turán graph has the maximum possible number of edges among all (''r'' + 1)-clique-free graphs with ''n'' vertices. Keevash and Sudakov (2003) show that the Turán graph is also the only (''r'' + 1)-clique-free graph of order ''n'' in which every subset of α''n'' vertices spans at least edges, if α is sufficiently close to 1. The Erdős–Stone theorem extends Turán's theorem by bounding the number of edges in a graph that does not have a fixed Turán graph as a subgraph. Via this theorem, similar bounds in extremal graph theory can be proven for any excluded subgraph, depending on the chromatic number of the subgraph. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Turán graph」の詳細全文を読む スポンサード リンク
|